//
// Created by vista on 2017/12/17.
//

#ifndef P_P18_H
#define P_P18_H

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
using namespace std;

class Solution {
public:

    void find_target(vector<vector<int>> & result, vector<int> & nums, int l,int r, int target){
        int c_l = l;
        int c_r = r;
        while (r > l){
            int left = nums[l];

            int mid = target - left ;
            auto ptr = binary_search(nums.begin() + l + 1, nums.begin() + r + 1, mid);
            if (ptr) {
                vector<int> tmp;
                tmp.push_back(nums[c_l - 1]);
                tmp.push_back(left);
                tmp.push_back(mid);
                tmp.push_back(nums[c_r + 1]);

                result.emplace_back(tmp);
            }

            do{
                ++l;
            }while (nums[l] == left);
            r = c_r;
        }
    }

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;

        if(nums.size() < 4)
            return result;

        sort(nums.begin(),nums.end());

        int l = 0, r = static_cast<int>(nums.size() - 1);

        while ( r-l >= 3) {
            int left = nums[l];
            do {
                int right = nums[r];
                int mid = target - left - right;

                find_target(result,nums,l+1,r-1,mid);

                do{
                    --r;
                }while (nums[r] == right);

            } while (r - l >= 3 );
            do{
                ++l;
            }while (nums[l] == left);
            r = static_cast<int>(nums.size() - 1);
        }

        return result;
    }
};

#endif //P_P18_H
